/**斐波那契数列: 0 1 1 2 3 5 8 ...
 * 输入3，输出2
 * 递归方法
 * 缺点：要一直循环计算
 * @param {*} n
 */
function fi(n) {
  if (n <= 1) {
    return n;
  }
  return fi(n - 1) + fi(n - 2);
}

/**
 * 数组循环方式，比递归好
 * @param {*} n
 */
function fi1(n) {
  let arr = new Array(n + 1).fill(0);
  arr[0] = 0;
  arr[1] = 1;
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  return arr[n];
}

// 闭包加循环加缓存
const fi2 = (function () {
  const cache = {
    0: 0,
    1: 1,
  };

  return function (n) {
    if (cache[n] != null) return cache[n];

    for (let i = 2; i <= n; i++) {
      cache[i] = cache[i - 1] + cache[i - 2];
    }

    return cache[n];
  };
})();

// egg
console.log(fi2(0)); // 0
console.log(fi2(1)); // 1
console.log(fi2(3)); // 2
console.log(fi2(5)); // 5
